/*
1、https://leetcode.cn/problems/house-robber-ii/
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0; // 没有房屋，返回0
        if (size == 1) return nums[0]; // 只有一个房屋，返回该房屋的金额

        // 计算线性排列房屋的最大抢劫金额的辅助函数
        auto robLinear = [](const vector<int>& nums) {
            int n = nums.size();
            if (n == 0) return 0; // 没有房屋，返回0
            if (n == 1) return nums[0]; // 只有一个房屋，返回该房屋的金额

            vector<int> dp(n, 0); // 动态规划数组
            dp[0] = nums[0]; // 只有一个房屋时的最大金额
            dp[1] = max(nums[0], nums[1]); // 两个房屋时的最大金额
            for (int i = 2; i < n; ++i) {
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); // 状态转移
            }
            return dp[n - 1]; // 返回最大抢劫金额
        };

        // 计算两种情况的最大抢劫金额：
        // 1. 排除第一个房屋，考虑范围 [1, size - 1]
        // 2. 排除最后一个房屋，考虑范围 [0, size - 2]
        int maxRob1 = robLinear(vector<int>(nums.begin() + 1, nums.end()));
        int maxRob2 = robLinear(vector<int>(nums.begin(), nums.end() - 1));

        return max(maxRob1, maxRob2); // 返回两种情况中的最大值
    }
};